/*
 * Copyright 2016 Scalified <http://www.scalified.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//package com.scalified.tree.multinode;
package com.gitee.wsl.struct.tree.multinode

import com.gitee.wsl.struct.list.LinkedList
import com.gitee.wsl.struct.tree.CategoryTreeNode
import com.gitee.wsl.struct.tree.TreeNode
import com.gitee.wsl.struct.tree.TreeNodeManager.linkParent
import com.gitee.wsl.struct.tree.TreeNodeManager.unlinkParent


/**
 * Implementation of the K-ary (multi node) tree data structure,
 * based on the leftmost-child-right-sibling representation
 *
 * @author shell
 * @version 1.0.0
 * @since 1.0.0
 */
open class LinkedMultiTreeNode(data: Any) : MultiTreeNode(data) {
    
    protected var treeNodes = LinkedList<TreeNode>()

    /**
     * Returns the collection of the child nodes of the current node
     * with all of its proper descendants, if any
     *
     *
     * Returns [Collections.emptySet] if the current node is leaf
     *
     * @return collection of the child nodes of the current node with
     * all of its proper descendants, if any;
     * [Collections.emptySet] if the current node is leaf
     */
    override fun subtrees(): List<TreeNode> {
        return treeNodes
        /*if (isLeaf()) {
            return Collections.emptySet();
        }
        Collection<TreeNode> subtrees = new LinkedHashSet<>();
        subtrees.add(leftMostNode);
        TreeNode nextSubtree = ((K) leftMostNode).rightSiblingNode;
        while (nextSubtree != null) {
            subtrees.add(nextSubtree);
            nextSubtree = ((K) nextSubtree).rightSiblingNode;
        }
        return subtrees;*/
    }

    /**
     * Adds the subtree with all of its descendants to the current tree node
     *
     *
     * `null` subtree cannot be added, in this case return result will
     * be `false`
     *
     *
     * Checks whether this tree node was changed as a result of the call
     *
     * @param subtree subtree to add to the current tree node
     * @return `true` if this tree node was changed as a
     * result of the call; `false` otherwise
     */
    override fun add(subtree: TreeNode): Boolean {
        linkParent(subtree, this as CategoryTreeNode)
        treeNodes.add(subtree)
        /*if (isLeaf()) {
            leftMostNode = subtree;
            lastSubtreeNode = leftMostNode;
        } else {
            if(lastSubtreeNode instanceof LinkedMultiTreeNode) {
                ((LinkedMultiTreeNode)lastSubtreeNode).rightSiblingNode = subtree;
                lastSubtreeNode = ((LinkedMultiTreeNode)lastSubtreeNode).rightSiblingNode;
            }else {
                if (lastSubtreeNode instanceof CategoryTreeNode) {
                    return ((CategoryTreeNode) lastSubtreeNode).add(lastSubtreeNode);
                }
                return false;
            }
        }*/return true
    }

    /**
     * Drops the first occurrence of the specified subtree from the current
     * tree node
     *
     *
     * Checks whether the current tree node was changed as a result of
     * the call
     *
     * @param subtree subtree to drop from the current tree node
     * @return `true` if the current tree node was changed as a result
     * of the call; `false` otherwise
     */
    override fun dropSubtree(subtree: TreeNode): Boolean {
        if (subtree.isRoot) {
            return false
        }
        unlinkParent(subtree)
        return treeNodes.remove(subtree)

        /*if (leftMostNode.equals(subtree)) {
            if(leftMostNode instanceof LinkedMultiTreeNode) {
                leftMostNode = ((LinkedMultiTreeNode) leftMostNode).rightSiblingNode;
                unlinkParent(subtree);
                ((LinkedMultiTreeNode) subtree).rightSiblingNode = null;
            }else{
                leftMostNode=rightSiblingNode;
                rightSiblingNode=null;
            }
            return true;
        } else {
            */
        /*LinkedMultiTreeNode nextSubtree = leftMostNode;
            while (nextSubtree.rightSiblingNode != null) {
                if (nextSubtree.rightSiblingNode.equals(subtree)) {
                    unlinkParent(subtree);
                    nextSubtree.rightSiblingNode = nextSubtree.rightSiblingNode.rightSiblingNode;
                    ((LinkedMultiTreeNode) subtree).rightSiblingNode = null;
                    return true;
                } else {
                    nextSubtree = nextSubtree.rightSiblingNode;
                }
            }*/
        /*
            TreeNodeIterator<TreeNode> items=iterator();
            while(items.hasNext()){
                TreeNode node=items.next();
                if(node instanceof CategoryTreeNode){
                    if(((CategoryTreeNode<?, ?>) node).dropSubtree(subtree))
                        return true;
                }
            };
        }
        return false;*/
    }

    /**
     * Removes all the subtrees with all of its descendants from the current
     * tree node
     */
    override fun clear() {
        treeNodes.forEach { treeNode: TreeNode -> unlinkParent(treeNode) }
        treeNodes.clear()
        /*if (!isLeaf()) {
            TreeNode nextNode = leftMostNode;
            while (nextNode != null) {
                unlinkParent(nextNode);
                if(nextNode instanceof LinkedMultiTreeNode) {
                    TreeNode nextNodeRightSiblingNode = ((LinkedMultiTreeNode)nextNode).rightSiblingNode;
                    ((LinkedMultiTreeNode)nextNode).rightSiblingNode = null;
                    ((LinkedMultiTreeNode)nextNode).lastSubtreeNode = null;
                    nextNode = nextNodeRightSiblingNode;
                }else{
                    if(nextNode instanceof CategoryTreeNode){
                        ((CategoryTreeNode)nextNode).clear();
                    }
                }
            }
            leftMostNode = null;
        }*/
    }

    /**
     * Checks whether the current tree node is a leaf, e.g. does not have any
     * subtrees
     *
     * @return `true` if the current tree node is a leaf, e.g. does not
     * have any subtrees; `false` otherwise
     */
    override val isLeaf: Boolean
        get() = treeNodes.isEmpty()

    /**
     * Checks whether among the current tree node subtrees there is
     * a specified subtree
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param subtree subtree whose presence within the current tree
     * node children is to be checked
     * @return `true` if among the current tree node subtrees
     * there is a specified subtree; `false` otherwise
     */
    override fun hasSubtree(subtree: TreeNode): Boolean {
        if ( isLeaf || subtree.isRoot) {
            return false
        }
        var hasItem = false
        if (treeNodes.contains(subtree)) hasItem = true else {
            for (treeNode in treeNodes) {
                if (treeNode is CategoryTreeNode) {
                    if (treeNode.hasSubtree(subtree)) {
                        hasItem = true
                        break
                    }
                }
            }
        }
        return hasItem

        /*TreeNode nextSubtree = leftMostNode;
        while (nextSubtree != null) {
            if (nextSubtree.equals(subtree)) {
                return true;
            } else {
                //nextSubtree = nextSubtree.rightSiblingNode;
                if(nextSubtree instanceof LinkedMultiTreeNode) {
                    ((LinkedMultiTreeNode)nextSubtree).rightSiblingNode = subtree;
                    nextSubtree = ((LinkedMultiTreeNode)nextSubtree).rightSiblingNode;
                }else {
                    if (nextSubtree instanceof CategoryTreeNode) {
                        return ((CategoryTreeNode) nextSubtree).hasSubtree(nextSubtree);
                    }
                    return false;
                }
            }
        }

        return false;*/
    }

    /**
     * Checks whether the current tree node with all of its descendants
     * (entire tree) contains the specified node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param node node whose presence within the current tree node with
     * all of its descendants (entire tree) is to be checked
     * @return `true` if the current node with all of its descendants
     * (entire tree) contains the specified node; `false`
     * otherwise
     */
    override operator fun contains(node: TreeNode): Boolean {
        if ( isLeaf || node.isRoot) {
            return false
        }
        var hasItem = false
        if (treeNodes.contains(node)) hasItem = true else {
            for (treeNode in treeNodes) {
                if (treeNode is CategoryTreeNode) {
                    if (treeNode.hasSubtree(node)) {
                        hasItem = true
                        break
                    }
                }
            }
        }
        return hasItem


        /*TreeNode nextSubtree = leftMostNode;
        while (nextSubtree != null) {
            if (nextSubtree.equals(node)) {
                return true;
            }
            if (nextSubtree.contains(node)) {
                return true;
            }
            //nextSubtree = nextSubtree.rightSiblingNode;
            if(nextSubtree instanceof LinkedMultiTreeNode) {
                nextSubtree = ((LinkedMultiTreeNode)nextSubtree).rightSiblingNode;
            }else {
                if (nextSubtree instanceof CategoryTreeNode) {
                    return ((CategoryTreeNode) nextSubtree).contains(nextSubtree);
                }
                return false;
            }
        }
        return false;*/
    }

    /**
     * Removes the first occurrence of the specified node from the entire tree,
     * starting from the current tree node and traversing in a pre order manner
     *
     *
     * Checks whether the current tree node was changed as a result of the call
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param node node to remove from the entire tree
     * @return `true` if the current tree node was changed as a result of
     * the call; `false` otherwise
     */
    override fun remove(node: TreeNode): Boolean {
        if ( isLeaf || node.isRoot) {
            return false
        }
        if (dropSubtree(node)) {
            return true
        }
        for (treeNode in treeNodes) {
            if (treeNode is CategoryTreeNode) {
                if (treeNode.remove(node)) {
                    return true
                }
            }
        }
        return false

        /*TreeNode nextSubtree = leftMostNode;
        while (nextSubtree != null) {
            if (nextSubtree.remove(node)) {
                return true;
            }
            //nextSubtree = nextSubtree.rightSiblingNode;
            if(nextSubtree instanceof LinkedMultiTreeNode) {
                nextSubtree = ((LinkedMultiTreeNode)nextSubtree).rightSiblingNode;
            }else {
                if (nextSubtree instanceof CategoryTreeNode) {
                    return ((CategoryTreeNode) nextSubtree).remove(nextSubtree);
                }
                return false;
            }
        }
        return false;*/
    }
    /**
     * Traverses the tree in a pre ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
    /*
    @Override
    public void traversePreOrder(TraversalAction<TreeNode> action) {
        if (!action.isCompleted()) {
            action.perform(this);
            if (!isLeaf()) {
                TreeNode nextNode = leftMostNode;
                while (nextNode != null) {
                    nextNode.traversePreOrder(action);
                    nextNode = nextNode.rightSiblingNode;
                }
            }
        }
    }

    */
    /**
     * Traverses the tree in a post ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
    /*
    @Override
    public void traversePostOrder(TraversalAction<TreeNode> action) {
        if (!action.isCompleted()) {
            if (!isLeaf()) {
                TreeNode nextNode = leftMostNode;
                while (nextNode != null) {
                    nextNode.traversePostOrder(action);
                    nextNode = nextNode.rightSiblingNode;
                }
            }
            action.perform(this);
        }
    }*/
    /**
     * Returns the height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     *
     *
     * Overridden to have a faster array implementation
     *
     * @return height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     */
    /* @Override
    public int height() {
        if (isLeaf()) {
            return 0;
        }
        int height = 0;
        TreeNode nextNode = leftMostNode;
        while (nextNode != null) {
            height = Math.max(height, nextNode.height());
            nextNode = nextNode.rightSiblingNode;
        }
        return height + 1;
    }*/
    /**
     * Returns the collection of nodes, which have the same parent
     * as the current node; [Collections.emptyList] if the current
     * tree node is root or if the current tree node has no subtrees
     *
     *
     * Overridden to have a faster array implementation
     *
     * @return collection of nodes, which have the same parent as
     * the current node; [Collections.emptyList] if the
     * current tree node is root or if the current tree node has
     * no subtrees
     */
    /*@Override
    public Collection<TreeNode> siblings() {
        if (isRoot()) {
            String message = String.format("Unable to find the siblings. The tree node %1$s is root", root());
            throw new TreeNodeException(message);
        }
        LinkedMultiTreeNode firstNode = ((LinkedMultiTreeNode) parent()).leftMostNode;
        if (firstNode.rightSiblingNode == null) {
            return Collections.emptySet();
        }
        Collection<LinkedMultiTreeNode> siblings = new LinkedHashSet<>();
        LinkedMultiTreeNode nextNode = firstNode;
        while (nextNode != null) {
            if (!nextNode.equals(this)) {
                siblings.add(nextNode);
            }
            nextNode = nextNode.rightSiblingNode;
        }
        return (Collection<K>) siblings;
    }*/

}